home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Graphics / 2D_3D / 2DLab / Source / voronoi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-12  |  4.4 KB  |  183 lines
  1. #include "headers.h"
  2.  
  3. int triangulate = FALSE, sorted, plot, debug = FALSE, randmode, outputmode;
  4. float xmin, xmax, ymin, ymax, deltax, deltay;
  5.  
  6. char execdir[80];
  7.  
  8. struct Site _sites[MAXSITES], *sites = _sites;
  9.  
  10. int nsites;
  11. int siteidx;
  12. int sqrt_nsites;
  13. int nvertices;
  14. struct Freelist sfl;
  15. struct Site *bottomsite;
  16.  
  17. int nedges;
  18. struct    Freelist efl;
  19.  
  20. struct Freelist    hfl;
  21. struct Halfedge *ELleftend, *ELrightend;
  22. int ELhashsize;
  23. struct Halfedge **ELhash;
  24.  
  25. int PQhashsize;
  26. struct Halfedge *PQhash;
  27. int PQcount;
  28. int PQmin;
  29.  
  30. /* sort sites on y, then x, coord */
  31. int scomp(s1,s2)
  32. struct Point *s1,*s2;
  33. {
  34.     if(s1->y < s2->y) return(-1);
  35.     if(s1->y > s2->y) return(1);
  36.     if(s1->x < s2->x) return(-1);
  37.     if(s1->x > s2->x) return(1);
  38.     return(0);
  39. }
  40.  
  41. /* sort GLsites on y, then x, coord */
  42. int GLscomp(s1,s2)
  43. VERT *s1,*s2;
  44. {
  45.     if(s1->y < s2->y) return(-1);
  46.     if(s1->y > s2->y) return(1);
  47.     if(s1->x < s2->x) return(-1);
  48.     if(s1->x > s2->x) return(1);
  49.     return(0);
  50. }
  51.  
  52. /* return a single in-storage site */
  53. struct Site *
  54. nextone()
  55. {
  56.     if(siteidx < nsites)
  57.     return (&sites[siteidx++]);
  58.     else
  59.     return( (struct Site *)NULL);
  60. }
  61.  
  62. sortGLsites()
  63. {
  64. float vx, vy;
  65. int k;
  66. char *a = NULL;
  67. float randr(), dx, dy;
  68.  
  69.     qsort((char *)GLsites, nsites, sizeof (VERT), GLscomp);
  70.  
  71.     /* check: are there coincident points? */
  72.     for (k = 1; k < nsites; k++)
  73.     if ((GLsites[k-1].y == GLsites[k].y) && (GLsites[k-1].x == GLsites[k].x))   {
  74. /*        printf ("coincident sites at %d, %d!\n", k-1, k);*/
  75.         dx = GLsites[k].x * (1.0 / 4096.0);
  76.         dy = GLsites[k].y * (1.0 / 4096.0);
  77.         /* hack: jitter the last point randomly in its last significant digit */
  78.         GLsites[k-1].x += randr (-dx, dx);
  79.         GLsites[k-1].y += randr (-dy, dy);
  80.         }
  81. }
  82.  
  83. /* implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,
  84.    deltax, deltay (can all be estimates).
  85.    Performance suffers if they are wrong; better to make nsites,
  86.    deltax, and deltay too big than too small.  (?) */
  87. voronoi (nextsite)
  88. struct Site *(*nextsite)();
  89. {
  90. struct Site *newsite, *bot, *top, *temp, *p;
  91. struct Site *v;
  92. struct Point newintstar;
  93. int pm;
  94. struct Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
  95. struct Edge *e;
  96.  
  97.     myfreeall ();
  98.  
  99.     if (nsites <= 1)
  100.     return;
  101.  
  102.     freeinit(&sfl, sizeof (struct Site));
  103.  
  104.     /* bboxinit();   /* copies static array into nsites */
  105.     geominit();        /* internal use of deltax, deltay  */
  106.  
  107.     PQinitialize();
  108.     bottomsite = (*nextsite)();
  109.     out_site(bottomsite);
  110.     ELinitialize();
  111.  
  112.     newsite = (*nextsite)();
  113.     while(1) {
  114.     if(!PQempty()) newintstar = PQ_min();
  115. /* new site is smallest */
  116.     if (newsite != (struct Site *)NULL && (PQempty() 
  117.          || newsite->coord.y < newintstar.y
  118.              || (newsite->coord.y == newintstar.y 
  119.                  && newsite->coord.x < newintstar.x))) {
  120.         out_site(newsite);
  121.         lbnd = ELleftbnd(&(newsite->coord));
  122.         rbnd = ELright(lbnd);
  123.         bot = rightreg(lbnd);
  124.         e = bisect(bot, newsite);
  125.         bisector = HEcreate(e, le);
  126.         ELinsert(lbnd, bisector);
  127.         if ((p = intersect(lbnd, bisector)) != (struct Site *) NULL) {
  128.         PQdelete(lbnd);
  129.         PQinsert(lbnd, p, dist(p,newsite));
  130.         }
  131.         lbnd = bisector;
  132.         bisector = HEcreate(e, re);
  133.         ELinsert(lbnd, bisector);
  134.         if ((p = intersect(bisector, rbnd)) != (struct Site *) NULL) {
  135.         PQinsert(bisector, p, dist(p,newsite));    
  136.         }
  137.         newsite = (*nextsite)();    
  138.     } else if (!PQempty()) {
  139.     /* intersection is smallest */
  140.         lbnd = PQextractmin();
  141.         llbnd = ELleft(lbnd);
  142.         rbnd = ELright(lbnd);
  143.         rrbnd = ELright(rbnd);
  144.         bot = leftreg(lbnd);
  145.         top = rightreg(rbnd);
  146.         out_triple(bot, top, rightreg(lbnd));
  147.         v = lbnd->vertex;
  148.         makevertex(v);
  149.         v_endpoint(lbnd->ELedge,lbnd->ELpm,v);
  150.         v_endpoint(rbnd->ELedge,rbnd->ELpm,v);
  151.         ELdelete(lbnd); 
  152.         PQdelete(rbnd);
  153.         ELdelete(rbnd); 
  154.         pm = le;
  155.         if (bot->coord.y > top->coord.y) {    
  156.         temp = bot; 
  157.         bot = top; 
  158.         top = temp; 
  159.         pm = re;
  160.         }
  161.         e = bisect(bot, top);
  162.         bisector = HEcreate(e, pm);
  163.         ELinsert(llbnd, bisector);
  164.         v_endpoint(e, re-pm, v);
  165.         deref(v);
  166.         if((p = intersect(llbnd, bisector)) != (struct Site *) NULL) {
  167.         PQdelete(llbnd);
  168.         PQinsert(llbnd, p, dist(p,bot));
  169.         }
  170.         if((p = intersect(bisector, rrbnd)) != (struct Site *) NULL) 
  171.         PQinsert(bisector, p, dist(p,bot));
  172.     } else 
  173.         break;
  174.     }
  175.  
  176.     for(lbnd=ELright(ELleftend); lbnd != ELrightend; lbnd=ELright(lbnd)) {
  177.     e = lbnd->ELedge;
  178.     out_ep(e);
  179.         }
  180. }
  181.  
  182.  
  183.